\begin{frame}
\frametitle{Grammars}

Matrix grammars for generating two dimensional languages are working as follows:

\begin{enumerate}
	\item Use a string grammar to generate a string of intermediate symbols
	\item These intermediate symbols are the start symbols for other grammars, which are generating vertical strings of terminals simultanously. 
\end{enumerate}

\end{frame}

\begin{frame}
\frametitle{Matrix grammars}

\begin{define}[XMG \cite{giftsironmoneyranisironmoney1972abstract}]
	$G = (G_H, G_V)$ is called XMG for $X \in \{PS, CS, CF, RL\}$ where 
	\begin{itemize}
		\item $G_H = (N_H, I, P_H, S)$ is a PSG, CSG, CFG or RLG with $N_H$ = a finite set of nonterminals, $I = \{S_1, \dots, S_k\}$ = a finite set of intermediates, $P_H$ = finite set of set of production rules and S = the start symbol. 
		\item $G_V = \bigcup_{i = 1}^k G_{i}$ where $G_{i} = (N_{i}, T, P_{i}, S_i)$ are right linear grammars with $T$ = finite set of terminals, $N_{i}$ = finite set of nonterminals ($N_{i} \cap N_{j} = \emptyset$ if $i \neq j$), $P_{i}$ = RL production rules and $S_i$ = start symbol. 
	\end{itemize}
\end{define}

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Derivation}

At first generate string $S_1 \dots S_n \in I^*$ from S. We write $S \overset{*}{\Rightarrow} S_1 \dots S_n$

For vertical derivation we write: 

\begin{center}
\[
\boxed{
\begin{aligned}
\begin{matrix}
S_1 & \dots & S_n
\end{matrix}
\end{aligned}
}
\]
$\Downarrow$
\[
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\
A_{1} & \dots & A_{n}
\end{matrix}
\end{aligned}
}
\]

\end{center}

for $S_j \rightarrow a_{1j}A_j$ are rules in $G_{j}, j \in \{1, \dots, k\}$ for $i = 1, \dots, n$

\begin{center}
\[
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-0.5ex]
a_{(r-1)1} & \dots & a_{(r-1)n} \\[-0.5ex]
A_1 & \dots & A_n
\end{matrix}
\end{aligned}
}\]
$\Downarrow$
\[
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-0.5ex]
a_{(r-1)1} & \dots & a_{(r-1)n} \\[-0.5ex]
a_{r1} & \dots & a_{rn} \\[-0.5ex]
B_1 & \dots & B_n
\end{matrix}
\end{aligned}
}\]
\end{center}

for $A_j \rightarrow a_{rj} B_j$ are rules in $G_{j}, j \in \{1, \dots, n\}$ for $i = 1, \dots, n$

\end{frame}

\begin{frame}
\frametitle{Derivation III}

If all rules $A_i \rightarrow a_{mi}$ are terminal rules, the derivation terminates. 

\begin{columns}
\begin{column}[l]{5cm}
\[
\boxed{
\begin{aligned}
\begin{matrix}
S_1 & \dots & S_n
\end{matrix}
\end{aligned}
}
\]
\begin{center}
$\Downarrow$
\end{center}
\[
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\
A_{1} & \dots & A_{n}
\end{matrix}
\end{aligned}
}
\]
\begin{center}
$\overset{*}{\Downarrow}$
\end{center}

\end{column}
\begin{column}[r]{5cm}
\[
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-1ex]
a_{(m-1)1} & \dots & a_{(m-1)n} \\[-0.5ex]
A_1 & \dots & A_n
\end{matrix}
\end{aligned}
}\]
\begin{center}
$\Downarrow$
\end{center}
\[
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-1ex]
a_{m1} & \dots & a_{mn}
\end{matrix}
\end{aligned}
}\]
\end{column}
\end{columns}

With $\overset{*}{\Downarrow}$ is the transitive closure of $\Downarrow$. 

\end{frame}

\begin{frame}
\frametitle{Matrix languages}

\begin{define}[XML]
If G is a PSMG (CSMG, CFMG, RLMG), then 
\begin{align*}
M(G) = \{m \times n \text{ arrays } (a_{ij}), i = 1, \dots m, j = 1, \dots, n \text{ and } m, n \geq 1\vert \\
S \overset{*}{\underset{G_H}{\Rightarrow}} S_1 \dots S_n \overset{*}{\underset{G_V}{\Downarrow}} (a_{ij})\}
\end{align*}
is a phrase structur matrix language (PSML), (CSML, CFML, RML). 
\end{define}

If L is the language generated by $G_H$ and $R_1, \dots, R_k$ the regular sets corresponding to $G_{i}, i = 1, \dots, k$, then we write $M(G) = (L)::(R_1, \dots, R_k)$

\end{frame}

\begin{frame}
\frametitle{Example}

\begin{Example}
$G = (G_H, G_V)$ is a CFMG with
\begin{itemize}
	\item $G_H = (\{S\}, \{S_1, S_2\}, \{S \rightarrow S_1SS_1, S \rightarrow S_2\}, S)$	
	\item $G_V = G_{1} \cup G_{2}$ where
	\begin{itemize}
		\item $G_{1} = (\{S_1, A\}, \{., X\}, \{S_1 \rightarrow XA, A \rightarrow .A, A \rightarrow X\}, S_1)$
		\item $G_{2} = (\{S_2\}, \{X\}, \{S_2 \rightarrow XS_2, S_2 \rightarrow X\}, S_2)$
	\end{itemize}
\end{itemize}
\end{Example}

Then $L = \{S_1^nS_2S_1^n \vert n \geq 1\}$, $R_1 = \{X.^nX \vert n \geq 1\}$, $R_2 = \{X^n \vert n \geq 1\}$ and $M(G) = (L)::(R_1, R_2)$. 

G generates pictures of shape \rotatebox{90}{H} of x's with .'s in between. 

\end{frame}

\begin{frame}
\frametitle{Example derivation}

\[
S \Rightarrow 
S_1SS_1 \overset{*}{\Rightarrow}
\boxed{
\begin{aligned}
\begin{matrix}
S_1 & S_1 & S_2 & S_1 & S_1 
\end{matrix}
\end{aligned}
}
\Downarrow
\boxed{
\begin{aligned}
\begin{matrix}
X & X & X & X & X \\[-0.5ex]
A & A & S_2 & A & A 
\end{matrix}
\end{aligned}
}
\]

\[
\Downarrow
\boxed{
\begin{aligned}
\begin{matrix}
X & X & X & X & X \\[-0.5ex]
. & . & X & . & . \\[-0.5ex]
A & A & S_2 & A & A 
\end{matrix}
\end{aligned}
}
\overset{*}{\Downarrow}
\boxed{
\begin{aligned}
\begin{matrix}
X & X & X & X & X \\[-0.5ex]
. & . & X & . & . \\[-0.5ex]
. & . & X & . & . \\[-0.5ex]
. & . & X & . & . \\[-0.5ex]
A & A & S_2 & A & A 
\end{matrix}
\end{aligned}
}
\Downarrow
\boxed{
\begin{aligned}
\begin{matrix}
X & X & X & X & X \\[-0.5ex]
. & . & X & . & . \\[-0.5ex]
. & . & X & . & . \\[-0.5ex]
. & . & X & . & . \\[-0.5ex]
X & X & X & X & X
\end{matrix}
\end{aligned}
}
\]

\end{frame}

\begin{frame}
\frametitle{Closure properties}

\begin{thm}
PSML (CSML, CFML, RML) is closed under
\begin{itemize}
	\item union
	\item concatenation
	\item Kleene closure
	\item $\epsilon$-free homomorphism
	\item inverse homomorphism
	\item intersection with regular matrices
\end{itemize}
\end{thm}

\begin{col}
	PSML (CSML, CFML, RML) is an abstract family of matrices. 
\end{col}

\end{frame}